package exercises.leetcode;

import exercises.newcoder.util.ListNode;

/**
 * <a href="https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/">
 * 19. 删除链表的倒数第 N 个结点</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 * <p>
 * 提示：
 * <ul>
 *   <li>链表中结点的数目为 sz</li>
 *   <li>1 <= sz <= 30</li>
 *   <li>0 <= Node.val <= 100</li>
 *   <li>1 <= n <= sz</li>
 * </ul>
 *
 * @author or2
 * @date 2021年09月24日 时间: 15:40
 */
public class No19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /*使用辅助头结点, 避免第一个结点特殊处理*/
        ListNode headAux = new ListNode(0, head);
        ListNode p = headAux;
        for (int i = 0; i <= n; i++) {
            p = p.next;
        }
        ListNode q = headAux;
        while (p != null) {
            p = p.next;
            q = q.next;
        }

        p = q.next;
        q.next = p.next;
        p.next = null;

        return headAux.next;
    }
}
